package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-17 14:44
 **/
public class LeetCode10 {

    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        //f[i][j]: 表示s的前i个字符串与p的前j个字符串是否匹配
        boolean[][] f = new boolean[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                //空正则只与空串匹配
                if (j == 0) {
                    f[i][j] = i == 0;
                } else {
                    //非*和*
                    if (p.charAt(j - 1) != '*') {
                        if (i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')) {
                            f[i][j] = f[i - 1][j - 1];
                        }
                    } else {
                        //不看*
                        if (j >= 2) {
                            f[i][j] = f[i][j - 2];
                        }
                        //如果看*与不看*有一个为true即为true
                        if (i > 0 && j > 1 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')) {
                            f[i][j] |= f[i - 1][j];
                        }
                    }
                }
            }
        }
        return f[n][m];
    }

}
